/**
 * 剑指 Offer 10- II. 青蛙跳台阶问题
 * https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/
 */

const mod = 1e9 + 7;

/**
 * @param {number} n
 * @return {number}
 */
function numWays(n) {
  if (n <= 1) {
    return 1;
  }
  let pre2 = 1;
  let pre1 = 1;
  for (let i = 2; i <= n; i += 1) {
    const cur = (pre2 + pre1) % mod;
    pre2 = pre1;
    pre1 = cur;
  }
  return pre1;
}

console.log(numWays(7) === 21);
console.log(numWays(100) === 782204094);
